import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import javax.swing.tree.TreeNode;


/*
 * @lc app=leetcode.cn id=94 lang=java
 *
 * [94] 二叉树的中序遍历
 *
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
 *
 * algorithms
 * Easy (75.57%)
 * Likes:    1231
 * Dislikes: 0
 * Total Accepted:    651.8K
 * Total Submissions: 862.4K
 * Testcase Example:  '[1,null,2,3]'
 *
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = []
 * 输出：[]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：root = [1]
 * 输出：[1]
 * 
 * 
 * 示例 4：
 * 
 * 
 * 输入：root = [1,2]
 * 输出：[2,1]
 * 
 * 
 * 示例 5：
 * 
 * 
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数目在范围 [0, 100] 内
 * -100 
 * 
 * 
 * 
 * 
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 递归
    // public List<Integer> inorderTraversal(TreeNode root) {
    //     List<Integer> arrayList = new ArrayList<>();
    //     if (root != null) {
    //         // 遍历左子树
    //         arrayList.addAll(inorderTraversal(root.left));
    //         arrayList.add(root.val);
    //         // 遍历右子树
    //         arrayList.addAll(inorderTraversal(root.right));
    //     }
    //     return arrayList;  
    // }

    // 迭代
    // public List<Integer> inorderTraversal(TreeNode root) {
    //     List<Integer> arrayList = new ArrayList<Integer>();
    //     Stack<TreeNode> stack = new Stack<>();
    //     TreeNode p = root;
    //     while (p != null || !stack.empty()) {
    //         if(p != null) {
    //             stack.push(p);
    //             p = p.left;
    //         } else {
    //             TreeNode treeNode = stack.pop();
    //             // 左孩子全部入栈后
    //             arrayList.add(treeNode.val); 
    //             p = treeNode.right;   
    //         }
    //     }
    //     return arrayList;
    // }

    // Morris遍历
    // 将根节点左子树的最右子树与根节点建立连接的算法
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> arrayList = new ArrayList<Integer>();
        while (root != null) {
            if (root.left != null) {
                // 暂存左子树的左节点
                TreeNode temp = root.left;
                // temp.right != root 表示已经建立连接了
                // 若没有建立连接且，则一直到左子树的最右节点
                while (temp.right != null && temp.right != root) {
                    temp = temp.right;
                }
                // 走到最右节点的情况
                if (temp.right == null) {
                    // 让其右指针与root建立连接
                    temp.right = root;
                    // 往左走继续建立连接
                    root = root.left;
                } 
                // 已经建立了连接的情况 (说明根节点的左子树已经访问完毕)
                else {
                    arrayList.add(root.val);
                    // 断开连接
                    temp.right = null;
                    // 接着访问下一个节点
                    root = root.right;
                }
            } 
            // 没有左子树，直接输出并访问右子树
            else {
                arrayList.add(root.val);
                root = root.right;
            }
        }
        return arrayList;
    }

}
// @lc code=end

